13.3 PAC-байесовские оценки риска

В предыдущем параграфе рассматривались равномерные оценки разницы истинного и эмпирического рисков. Если в рассматриваемом классе моделей есть «плохие», то равномерные оценки становятся слишком пессимистичными. Часто нельзя гарантировать, что что наш алгоритм обучения их никогда не выбирает, поэтому класс моделей F\mathcal{F} для равномерной оценки не получится сузить до класса только «хороших» моделей. Но можно надеяться, что плохие выучиваются не слишком часто. Например, известно, что градиентный спуск обычно сходится к хорошим моделям (об этом мы ещё поговорим в параграфе про implicit bias). В этом параграфе мы разберём элегантный способ учесть «предпочтения» алгоритма обучения в оценке разницы рисков.

Вспомним равномерную оценку для конечного F\mathcal{F}:

P(supfF(R(f)R^m(f))ϵ)=P(fF:  (R(f)R^m(f))ϵ)\mathbb{P}\left(\sup_{f\in\mathcal{F}} (R(f) - \hat R_m(f)) \geq \epsilon\right) = \mathbb{P}\left(\exists f\in\mathcal{F}: \; (R(f) - \hat R_m(f)) \geq \epsilon\right) \leq

fFP(R(f)R^m(f)ϵ)Fe2mϵ2ϵ>0,\leq \sum_{f\in\mathcal{F}} \mathbb{P}(R(f) - \hat R_m(f) \geq \epsilon) \leq \vert\mathcal{F}\vert e^{-2 m \epsilon^2} \quad \forall \epsilon > 0,

где F\vert\mathcal{F}\vert – мощность класса F\mathcal{F}. Эта оценка формально верна и для бесконечного F\mathcal{F}, но смысл её теряется. Давайте попробуем исправить это.

Вступайте в сообщество хендбука

Здесь можно найти единомышленников, экспертов и просто интересных собеседников. А ещё — получить помощь или поделиться знаниями.

Пусть F\mathcal{F} не более, чем счётно. Для каждого fFf \in \mathcal{F} возьмём своё ϵ(f)\epsilon(f). Если взять ϵ(f)\epsilon(f) таким, чтобы fFe2mϵ2(f)\sum_{f \in \mathcal{F}} e^{-2 m \epsilon^2(f)} было конечным, то приходим к осмысленной оценке:

P(fF:  (R(f)R^m(f))ϵ(f))\mathbb{P}\left(\exists f\in\mathcal{F}: \; (R(f) - \hat R_m(f)) \geq \epsilon(f)\right) \leq

fFP(R(f)R^m(f)ϵ(f))fFe2mϵ2(f).\sum_{f\in\mathcal{F}} \mathbb{P}\left(R(f) - \hat R_m(f) \geq \epsilon(f)\right) \leq \sum_{f \in \mathcal{F}} e^{-2 m \epsilon^2(f)}.

Рассмотрим теперь некоторое вероятностное распределение P(f)P(f) на F\mathcal{F}. В качестве ϵ(f)\epsilon(f) возьмём

e2mϵ2(f)=P(f)e2mϵ~2,e^{-2 m \epsilon^2(f)} = P(f) e^{-2 m \tilde\epsilon^2},

где ϵ~R+\tilde\epsilon \in \mathbb{R}_+. Из этого уравнения получаем следующее выражение для ϵ(f)\epsilon(f):

ϵ(f)=ϵ~2+12mlog1P(f).\epsilon(f) = \sqrt{\tilde\epsilon^2 + \frac{1}{2m} \log\frac{1}{P(f)}}.

В итоге, для любого ϵ~>0\tilde\epsilon > 0 получаем оценку:

P(fF:  (R(f)R^m(f))ϵ~2+12mlog1P(f))e2mϵ~2.\mathbb{P}\left(\exists f\in\mathcal{F}: \; (R(f) - \hat R_m(f)) \geq \sqrt{\tilde\epsilon^2 + \frac{1}{2m} \log\frac{1}{P(f)}}\right) \leq e^{-2 m \tilde\epsilon^2}.

Или, что то же самое, с вероятностью 1δ\geq 1 - \delta по SmS_m для любого fFf \in \mathcal{F}:

R(f)R^m(f)12m(log1δ+log1P(f))R(f)-\hat{R}_m(f)\leq\sqrt{\frac{1}{2m}\left(\log\frac{1}{\delta}+\log\frac{1}{P(f)}\right)}

Заметим, что если F\mathcal{F} конечно, а P(f)P(f) – равномерное распределение, то оценка выше совпадает с равномерной оценкой. Если же наш алгоритм обучения предпочитает выбирать модели, для которых P(f)P(f) велико, то оценка улучшается по сравнению с равномерной. Таким образом, распределение P(f)P(f) «кодирует» наши представления о предпочтениях алгоритма. Будем называть P(f)P(f) «априорным распределением».

Как обобщить оценку выше на несчётные классы моделей? В первую очередь, предположим, что наш алгоритм обучения A\mathcal{A} стохастичен, а значит, на выходе даёт не одну модель, а распределение:

f^mQ^m=A(Sm).\hat f_m \sim \hat Q_m = \mathcal{A}(S_m).

Будем называть это распределение «апостериорным». Такое рассуждение осмысленно, например, для стохастического градиентного спуска: очевидно, что результат его работы на невыпуклой функции потерь недетерминирован (он может сходиться в разные локальные минимумы).

Заметим, что главное отличие апостериорного распределения от априорного в том, что первое зависит от данных, а второе – нет. Важно понимать при этом, что, несмотря на названия, эти два распределения не связаны между собой никаким вариантом формулой Байеса. Сходство с байесовским подходом скорее внешнее. Поэтому слова «априорное» и «апостериорное» имеет смысл писать в кавычках, но для экономии места мы их будем в дальнейшем опускать.

Оценки разности рисков, о которых речь пойдёт ниже, называются PAC-байесовскими (PAC-bayesian, где PAC – probably approximately correct).

Сформулируем одну из классических оценок из этого класса:

Теорема Макаллестера. Пусть F\mathcal{F} – множество моделей и PP – распределение на F\mathcal{F}. Тогда для любого δ(0,1)\delta \in (0,1) с вероятностью 1δ\geq 1 - \delta по SmS_m имеем:

R(Q^m)R^m(Q^m)+12m1(log4mδ+KL(Q^m  P)),R(\hat Q_m) \leq \hat R_m(\hat Q_m) + \sqrt{\frac{1}{2m-1} \left(\log \frac{4m}{\delta} + \mathrm{KL}(\hat Q_m\;\vert\vert P) \right)},

где R(Q)=EfQR(f)R(Q) = \mathbb{E}_{f \sim Q} R(f) и R^m(Q)=EfQR^m(f)\hat R_m(Q) = \mathbb{E}_{f \sim Q} \hat R_m(f).

Видим, что оценка тем лучше, чем ближе апостериорное распределение к априорному. Здесь работает следующая интуиция. Если для большинства обучающих наборов данных апостериорное распределение близко к априорному, то оно почти не зависит от данных, а значит, истинный риск и риск на обучающей выборке должны быть близки с высокой вероятностью. Если же апостериорное зависит от данных сильно, то, скорее всего, модель сильно переобучается, а значит, оценка не может быть хорошей; в нашем случае она велика из-за большой KL-дивергенции.

Для доказательства теоремы нам понадобятся две леммы:

Лемма 1. Для любого распределения PP на F\mathcal{F} и для любого δ(0,1)\delta \in (0,1) с вероятностью 1δ\geq 1 - \delta по SmS_m имеем:

EfPe(2m1)(Δm(f))24mδ,\mathbb{E}_{f \sim P} e^{(2m-1) (\Delta_m(f))^2} \leq \frac{4m}{\delta},

где Δm(f)=R(f)R^m(f)\Delta_m(f) = \vert R(f) - \hat R_m(f)\vert.

Лемма 2 (лемма Донскера-Вередана, Donsker-Varadhan). Пусть PP и QQ – вероятностные распределения на множестве XX. Тогда для любого h:  XRh: \; X \to \mathbb{R}

ExQh(x)logExPeh(x)+KL(QP).\mathbb{E}_{x\sim Q} h(x) \leq \log\mathbb{E}_{x \sim P} e^{h(x)} + \mathrm{KL}(Q\vert\vert P).

Доказательство теоремы

Применим лемму 2 к X=FX = \mathcal{F}, h=(2m1)Δm2h = (2m-1) \Delta_m^2 и Q=Q^mQ = \hat Q_m:

EfQ^m(2m1)(Δm(f))2logEfPe(2m1)(Δm(f))2+KL(Q^m    P). \mathbb{E}_{f \sim \hat Q_m} (2m-1) (\Delta_m(f))^2 \leq \log\mathbb{E}_{f \sim P} e^{(2m-1) (\Delta_m(f))^2} + \mathrm{KL}(\hat Q_m\;\vert\vert\;P).

Тогда по лемме 1 с вероятностью 1δ\geq 1 - \delta по SmS_m имеем:

EfQ^m(2m1)(Δm(f))2log4mδ+KL(Q^m    P). \mathbb{E}_{f \sim \hat Q_m} (2m-1) (\Delta_m(f))^2 \leq \log\frac{4m}{\delta} + \mathrm{KL}(\hat Q_m\;\vert\vert\;P).

Доказательство, таким образом, легко завершается:

R(Q^m)R^m(Q^m)EfQ^m(R(f)R^m(f)) R(\hat Q_m) - \hat R_m(\hat Q_m) \leq \vert\mathbb{E}_{f\sim \hat Q_m} (R(f) - \hat R_m(f))\vert \leq

EfQ^mR(f)R^m(f)=EfQ^mΔm(f)\leq\mathbb{E}_{f\sim \hat Q_m} |R(f) - \hat R_m(f)| = \mathbb{E}_{f\sim \hat Q_m} \Delta_m(f) \leq

EfQ^m(Δm(f))2 \leq\sqrt{\mathbb{E}_{f\sim \hat Q_m} (\Delta_m(f))^2} \leq

12m1(log4mδ+KL(Q^m    P)). \sqrt{\frac{1}{2m-1} \left(\log \frac{4m}{\delta} + \mathrm{KL}(\hat Q_m\;\vert\vert\;P) \right)}.

Доказательство леммы 2

Мы рассмотрим лишь простой случай, когда и у PP, и у QQ есть плотности, и они нигде не обращаются в ноль.

ExQh(x)KL(QP)=ExQ(h(x)log(q(x)p(x)))= \mathbb{E}_{x \sim Q} h(x) - \mathrm{KL}(Q\vert\vert P) = \mathbb{E}_{x \sim Q} \left(h(x) - \log\left(\frac{q(x)}{p(x)}\right)\right) =

=ExQlog(eh(x)p(x)q(x))logExQ(eh(x)p(x)q(x))=logExPeh(x). =\mathbb{E}_{x \sim Q} \log\left(e^{h(x)} \frac{p(x)}{q(x)}\right) \leq \log \mathbb{E}_{x \sim Q} \left(e^{h(x)} \frac{p(x)}{q(x)}\right) = \log \mathbb{E}_{x \sim P} e^{h(x)}.

Доказательство леммы 1

Нам понадобится

Неравенство Маркова. Пусть XX – неотрицательная случайная величина. Тогда для любого a>0a > 0 имеем

P(Xa)EXa. \mathbb{P}(X \geq a) \leq \frac{\mathbb{E} X}{a}.

В качестве XX и aa из неравенства Маркова возьмём

X=EfPe(2m1)(Δm(f))2,a=4m/δX = \mathbb{E}_{f \sim P} e^{(2m-1) (\Delta_m(f))^2},\qquad a = 4m / \delta

Тогда

P(14EfPe(2m1)(Δm(f))24mδ)\mathbb{P}\left(\vphantom{\frac14}\mathbb{E}_{f \sim P} e^{(2m-1) (\Delta_m(f))^2} \leq \frac{4m}{\delta}\right) \leq

δ4mESmEfPe(2m1)(Δm(f))2\leq\frac{\delta}{4m}\mathbb{E}_{S_m} \mathbb{E}_{f \sim P} e^{(2m-1) (\Delta_m(f))^2}

Значит, нам достаточно доказать, что

ESmEfPe(2m1)(Δm(f))24m. \mathbb{E}_{S_m} \mathbb{E}_{f \sim P} e^{(2m-1) (\Delta_m(f))^2} \leq 4m.

Мы докажем даже более сильное соотношение:

ESme(2m1)(Δm(f))24mfF\mathbb{E}_{S_m}e^{(2m-1)(\Delta_m(f))^2}\leq4m\quad\forall f\in\mathcal{F}

Заметим, что из неравенства Хёффдинга будет следовать

PSm(Δm(f)ϵ)2e2mϵ2ϵ>0fF\mathbb{P}_{S_m}(\Delta_m(f)\geq\epsilon)\leq2e^{-2m\epsilon^2}\quad\forall\epsilon>0\quad\forall f\in\mathcal{F}

Для простоты предположим, что распределение Δm(f)\Delta_m(f) имеет плотность для любого fFf \in \mathcal{F}; обозначим её pf(Δ)p_f(\Delta). В этом случае мы можем ограничить матожидания по SmS_m напрямую:

ESme(2m1)(Δm(f))2=0e(2m1)ϵ2pf(ϵ)dϵ= \mathbb{E}_{S_m} e^{(2m-1) (\Delta_m(f))^2} = \int_0^\infty e^{(2m-1) \epsilon^2} p_f(\epsilon) \, d\epsilon =

0e(2m1)ϵ2ddϵ(ϵpf(Δ)dΔ)dϵ= \int_0^\infty e^{(2m-1) \epsilon^2} \frac{d}{d\epsilon} \left(-\int_\epsilon^\infty p_f(\Delta) \, d\Delta\right) \, d\epsilon =

=(e(2m1)ϵ2ϵpf(Δ)dΔ)ϵ=0+2(2m1)0ϵe(2m1)ϵ2ϵpf(Δ)dΔdϵ = \left.-\left(e^{(2m-1) \epsilon^2} \int_\epsilon^\infty p_f(\Delta) \, d\Delta\right) \right|_{\epsilon=0}^\infty + 2 (2m-1) \int_0^\infty \epsilon\,e^{(2m-1) \epsilon^2} \int_\epsilon^\infty p_f(\Delta) \, d\Delta \, d\epsilon \leq

0pf(Δ)dΔ+2(2m1)0ϵe(2m1)ϵ2ϵpf(Δ)dΔdϵ \leq \int_0^\infty p_f(\Delta) \, d\Delta + 2 (2m-1) \int_0^\infty \epsilon\,e^{(2m-1) \epsilon^2} \int_\epsilon^\infty p_f(\Delta) \, d\Delta \, d\epsilon \leq

2+4(2m1)0ϵe(2m1)ϵ2e2mϵ2dϵ= \leq 2 + 4 (2m-1) \int_0^\infty \epsilon\,e^{(2m-1) \epsilon^2} e^{-2m \epsilon^2} \, d\epsilon =

2+4(2m1)0ϵeϵ2dϵ=2+2(2m1)=4m. 2 + 4 (2m-1) \int_0^\infty \epsilon\,e^{-\epsilon^2} \, d\epsilon = 2 + 2 (2m-1) = 4m.

В общем случае, мы не можем предполагать наличие плотности у Δm(f)\Delta_m(f). Доказательство в этом случае можно найти в оригинальной работе D. A. McAllester Some pac-bayesian theorems, а также в конспекте лекций автора этого параграфа.

Теорема Макаллестера – не единственная из возможных пак-байесовских оценок. Например, несколько улучшенную версию той же оценки можно найти в работе Bounds for averaging classifiers. Другие оценки подобного типа можно найти в монографии PAC-Bayesian supervised classification: the thermodynamics of statistical learning.

Применение пак-байесовских оценок к детерминированным алгоритмам обучения

Выше были рассмотрены две PAC-байесовские оценки: одна для не более, чем счётного множества моделей, другая – для произвольного. За возможность использования несчётных классов моделей мы заплатили тем, что алгоритм обучения должен быть недетерминированным (для детерминированных алгоритмов KL-дивергенция в Теореме Макаллестера может вырождаться в бесконечность; например, это так, если априорное распределение гауссово). Чаще всего класс моделей F\mathcal{F} всё-таки несчетён: например, если это класс всех сетей фиксированной архитектуры, то он индексируется весами, которых несчётное множество. При этом, хотя используемый алгоритм обучения и в самом деле недетерминирован (стохастический градиентный спуск зависит от случайного выбора батчей и от инициализации весов) и теорема Макаллестера выполняется, финальное распределение моделей очень сложно охарактеризовать, и из-за этого непонятно, как считать KL-дивергенцию.

Предположим, что алгоритм обучения всё-таки детерминирован; этого можно добиться, зафиксировав сид генератора случайных чисел при обучении. Как получить осмысленную PAC-байесовскую оценку для детерминированного алгоритма на несчётном множестве моделей?

Мы рассмотрим два способа.

Первый способ – добавить известный шум в финальную модель, выданную детерминированным алгоритмом. Так, для нейронных сетей, результатом работы алгоритма обучения является набор весов. Если добавить в этот набор гауссовский шум, а также в качестве априорного распределения взять гауссовское, то KL-дивергенцию в теореме Макаллестера можно будет посчитать аналитически.

Дисперсию шума в апостериорном распределении тоже можно обучить с помощью градиентного спуска одновременно с весами, тем самым минимизируя правую часть оценки из вышеупомянутой теоремы. Если в найденную модель удастся добавить шум так, чтобы KL-дивергенция значительно уменьшилась, но при этом риск на обучающей выборке не сильно вырос, то оценка на истинный риск получится хорошей.

Это рассуждение связывает PAC-байесовские оценки и гипотезу о том, что «плоские» («широкие») минимумы хорошо обобщают. В самом деле, если минимум «плоский», то в модель из него можно добавить много шума, не испортив качество на обучении. Оценки, основанные на этом принципе, можно найти в работах Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data и A PAC-Bayesian Approach to Spectrally-Normalized Margin Bounds for Neural Networks.

Второй способ состоит в том, чтобы взять дискретное кодирование cc и применить дискретную PAC-байесовскую оценку к закодированной модели вместо оригинальной. Обозначим закодированную модель ff через fcf_c. Следуя работе Non-vacuous Generalization Bounds at the ImageNet Scale: a PAC-Bayesian Compression Approach, возьмём априорное распределение с массой, убывающей с ростом длины кода:

Pc(fc)=1Zm(fc)2fc.P_c(f_c) = \frac{1}{Z} m(\vert f_c\vert ) 2^{-|f_c|}.

Здесь fc\vert f_c\vert – длина кода модели ff, m(k)m(k) – некоторое вероятностное распределение на N\mathbb{N}, а ZZ – нормализующая константа. Тогда KL-дивергенция примет следующий вид:

KL(δfcPc)=logZ+fclog2log(m(fc)).\mathrm{KL}(\delta_{f_c}\vert\vert {P_c}) = \log Z + \vert f_c\vert \log 2 - \log(m(\vert f_c\vert )).

Для того, чтобы KL-дивергенция выше была как можно меньше, необходимо, чтобы наш алгоритм обучения на реалистичных данных сходился в модели с маленькой длиной кода. Для этого будем применять наше кодирование не к оригинальной модели, а к сжатой с помощью некоторого алгоритма сжатия. Здесь мы предполагаем, что модели, к которым сходится наш алгоритм обучения, можно сжать с малыми потерями до моделей с малой длиной кода. Другими словами, мы опираемся на предположение, что обученные модели в некоторым смысле «простые».

Если модель параметризована весами θ\theta, типичный алгоритм сжатия выдаст набор (S,Q,C)(S,Q,C), где

  • S=s1:k[dimθ]S = s_{1:k} \subset [\dim\theta] – позиции ненулевых весов;
  • C=c1:rRC = c_{1:r} \subset \mathbb{R} – «словарь» весов;
  • Q=q1:kQ = q_{1:k}, qi[r]q_i \in [r] i[k]\forall i \in [k] – квантизованные значения весов.

Выход алгоритма будет выглядеть как C(θ)i=cqj\mathcal{C}(\theta)_i = c_{q_j}, если i=sji = s_j, иначе 00.

Тогда наивное 32-битное кодирование даст следующую длину:

C(θ)c=Sc+Qc+Cck(logdimθ+logr)+32r.\vert\mathcal{C}(\theta)\vert_c = \vert S\vert_c + \vert Q\vert_c + \vert C\vert_c \leq k (\log\dim\theta + \log r) + 32 r.

В работе Non-vacuous Generalization Bounds at the ImageNet Scale: a PAC-Bayesian Compression Approach описанный выше способ применяется к модели MobileNet (свёрточной сети, сконструированной специально для мобильных устройств), обученной на наборе данных ImageNet, и получают верхнюю оценку на истинный риск, равную 96.5%96.5\% (риск случайного угадывания – 99.9%99.9\%). Хотя такой результат и выглядит очень скромным, но это первая осмысленная оценка обобщающей способности реально используемой нейронной сети на реалистичном наборе данных.

Чтобы добавить в заметки выделенный текст, нажмите Command + E
Загрузка...
Предыдущий параграф13.2. Обобщающая способность – классическая теория
Следующий параграф13.4. Сети бесконечной ширины